package org.czl.leetcode4;

import java.util.Arrays;

public class l790 {
    public static void main(String[] args) {
       // System.out.println(numTilings(4));
        int[][] base = new int[][]{
                {2,1,0},
                {0,0,1},
                {1,0,0}
        };
        int[][] ans = new int[][]{{5,2,1}};
        System.out.println(Arrays.deepToString(mu(ans, base)));
    }
    static int MOD = 1_000_000_007;
    static int[][] mu(int[][] a, int[][] b){
        int m = a.length;
        int n = b[0].length;
        int k = b.length;
        int[][] ans = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                for(int z = 0; z < k; z++){
                    ans[i][j] += (a[i][z] * b[z][j]) % MOD;

                }
            }
        }
        return ans;
    }
    public static int numTilings(int n) {
        if(n == 1)return 1;
        if(n == 2)return 2;
        if(n == 3)return 5;
        int[][] base = new int[][]{
                {2,1,0},
                {0,0,1},
                {1,0,0}
        };

        int[][] ans = new int[][]{{5,2,1}};//第3 2 1项答案 所以答案是n - 2;
        int[][] m = new int[3][3];
        m[0][0] = 1; m[1][1] = 1; m[2][2] = 1;
        while(n > 0){
            if((n & 1) == 1){
                m = mu(base, m);
            }
            base = mu(base, base);
            n >>= 1;
        }
        System.out.println(1);
        return mu(ans, base)[0][2];
    }
}
